Prasanna, “Collaborative scheduling of dag structured computations on multi-core processors

Many computational solutions can be expressed as DAGs, in which the nodes represent tasks to be executed. A fundamental challenge in parallel computing on multicore processors is to schedule such DAGs onto multiple cores without violating the precedence constraints. In this paper, we propose a lightweight scheduling framework for directed acyclic graph (DAG) structured computations on state-of-the-art multicore processors. We present a self-scheduling method called collaborative scheduling to dynamically allocate tasks to the cores. The scheduling activity is distributed across the threads. Various scheduling policies and application-specific optimizations can be integrated into our framework. To reduce scheduling overheads and balance the workload across the threads, we propose an efficient lock-free local task list organization. We experimentally evaluated the collaborative scheduler with lock-free local task lists against a lock-based version, a straightforward self-scheduling version and several centralized scheduling methods on various multicore processors